18. 4Sum.go

package leetcode

import"sort"

// 解法一 双指针
funcfourSum(nums []int, targetint) (quadruplets [][]int) {
sort.Ints(nums)
n:=len(nums)
fori:=0; i<n-3&&nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <=target; i++ {
ifi>0&&nums[i] ==nums[i-1] ||nums[i]+nums[n-3]+nums[n-2]+nums[n-1] <target {
continue
 }
forj:=i+1; j<n-2&&nums[i]+nums[j]+nums[j+1]+nums[j+2] <=target; j++ {
ifj>i+1&&nums[j] ==nums[j-1] ||nums[i]+nums[j]+nums[n-2]+nums[n-1] <target {
continue
 }
forleft, right:=j+1, n-1; left<right; {
ifsum:=nums[i] +nums[j] +nums[left] +nums[right]; sum==target {
quadruplets=append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]})
forleft++; left<right&&nums[left] ==nums[left-1]; left++ {
 }
forright--; left<right&&nums[right] ==nums[right+1]; right-- {
 }
 } elseifsum<target {
left++
 } else {
right--
 }
 }
 }
 }
return
}

// 解法二 kSum
funcfourSum1(nums []int, targetint) [][]int {
res, cur:=make([][]int, 0), make([]int, 0)
sort.Ints(nums)
kSum(nums, 0, len(nums)-1, target, 4, cur, &res)
returnres
}

funckSum(nums []int, left, rightint, targetint, kint, cur []int, res*[][]int) {
ifright-left+1<k||k<2||target<nums[left]*k||target>nums[right]*k {
return
 }
ifk==2 {
// 2 sum
twoSum(nums, left, right, target, cur, res)
 } else {
fori:=left; i<len(nums); i++ {
ifi==left|| (i>left&&nums[i-1] !=nums[i]) {
next:=make([]int, len(cur))
copy(next, cur)
next=append(next, nums[i])
kSum(nums, i+1, len(nums)-1, target-nums[i], k-1, next, res)
 }
 }
 }

}

functwoSum(nums []int, left, rightint, targetint, cur []int, res*[][]int) {
forleft<right {
sum:=nums[left] +nums[right]
ifsum==target {
cur=append(cur, nums[left], nums[right])
temp:=make([]int, len(cur))
copy(temp, cur)
*res=append(*res, temp)
// reset cur to previous state
cur=cur[:len(cur)-2]
left++
right--
forleft<right&&nums[left] ==nums[left-1] {
left++
 }
forleft<right&&nums[right] ==nums[right+1] {
right--
 }
 } elseifsum<target {
left++
 } else {
right--
 }
 }
}

// 解法三
funcfourSum2(nums []int, targetint) [][]int {
res:= [][]int{}
counter:=map[int]int{}
for_, value:=rangenums {
counter[value]++
 }

uniqNums:= []int{}
forkey:=rangecounter {
uniqNums=append(uniqNums, key)
 }
sort.Ints(uniqNums)

fori:=0; i<len(uniqNums); i++ {
if (uniqNums[i]*4==target) &&counter[uniqNums[i]] >=4 {
res=append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[i]})
 }
forj:=i+1; j<len(uniqNums); j++ {
if (uniqNums[i]*3+uniqNums[j] ==target) &&counter[uniqNums[i]] >2 {
res=append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[j]})
 }
if (uniqNums[j]*3+uniqNums[i] ==target) &&counter[uniqNums[j]] >2 {
res=append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[j]})
 }
if (uniqNums[j]*2+uniqNums[i]*2==target) &&counter[uniqNums[j]] >1&&counter[uniqNums[i]] >1 {
res=append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j], uniqNums[j]})
 }
fork:=j+1; k<len(uniqNums); k++ {
if (uniqNums[i]*2+uniqNums[j]+uniqNums[k] ==target) &&counter[uniqNums[i]] >1 {
res=append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j], uniqNums[k]})
 }
if (uniqNums[j]*2+uniqNums[i]+uniqNums[k] ==target) &&counter[uniqNums[j]] >1 {
res=append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[k]})
 }
if (uniqNums[k]*2+uniqNums[i]+uniqNums[j] ==target) &&counter[uniqNums[k]] >1 {
res=append(res, []int{uniqNums[i], uniqNums[j], uniqNums[k], uniqNums[k]})
 }
c:=target-uniqNums[i] -uniqNums[j] -uniqNums[k]
ifc>uniqNums[k] &&counter[c] >0 {
res=append(res, []int{uniqNums[i], uniqNums[j], uniqNums[k], c})
 }
 }
 }
 }
returnres
}